﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Text;

namespace Acoris.Foundation
{
    /// <summary>
    /// 表示一颗四叉树
    /// </summary>
    /// <typeparam name="T">节点索引的数据类型</typeparam>
    public sealed class QuadTree<T>
    {
        #region Node<E> Definition

        public sealed class Node<E>
        {
            public NodeData<E> Data;
            public Boundary Boundary;
            internal readonly Node<E>[] NodeArray;
            public IList<NodeData<E>> Value;
            internal byte height;
            internal int count;

            public Node(Boundary boundary)
            {
                this.Boundary = boundary;
                this.Value = new List<NodeData<E>>();
                NodeArray = new Node<E>[4];
            }

            public Node<E> NW {
                get { return NodeArray[0]; }
                set { NodeArray[0] = value; }
            }

            public Node<E> NE {
                get { return NodeArray[1]; }
                set { NodeArray[1] = value; }
            }

            public Node<E> SW {
                get { return NodeArray[2]; }
                set { NodeArray[2] = value; }
            }

            public Node<E> SE {
                get { return NodeArray[3]; }
                set { NodeArray[3] = value; }
            }
        }

        #endregion

        #region NodeData<E> Definition

        public sealed class NodeData<E>
        {
            public Boundary Boundary;
            public E Data;

            public NodeData(Boundary boundary, E data)
            {
                this.Boundary = boundary;
                this.Data = data;
            }
        }

        #endregion

        #region QuadTreeEnumerator

        public struct QuadTreeEnumerator : IEnumerator<NodeData<T>>
        {
            public NodeData<T> Current { get => throw new NotImplementedException(); }
            object IEnumerator.Current { get => throw new NotImplementedException(); }

            public void Dispose()
            {
                throw new NotImplementedException();
            }

            public bool MoveNext()
            {
                throw new NotImplementedException();
            }

            public void Reset()
            {
                throw new NotImplementedException();
            }
        }

        #endregion

        #region Locate / CreateNode / Split / Insert

        internal static int Locate(Node<T> node,Boundary boundary)
        {
            var originX = node.Boundary.X;
            var originY = node.Boundary.Y;
            var originWidth = node.Boundary.Width;
            var originHeight = node.Boundary.Height;
            var halfWidth = originWidth /2f;
            var halfHeight = originHeight /2f;
            var centerX = originX + halfWidth;
            var centerY = originY + halfHeight;
            var flag1 = ( boundary.X < centerX && boundary.X >= 0)?0:1;
            var flag2 = ( boundary.Y < centerY && boundary.Y >= 0)?0:1;

            return (flag2 << 1) + flag1;
        }

        internal static int Locate(Node<T> node,Point point)
        {
            var originX = node.Boundary.X;
            var originY = node.Boundary.Y;
            var originWidth = node.Boundary.Width;
            var originHeight = node.Boundary.Height;
            var halfWidth = originWidth /2f;
            var halfHeight = originHeight /2f;
            var centerX = originX + halfWidth;
            var centerY = originY + halfHeight;
            var flag1 = ( point.X < centerX && point.X >= 0)?0:1;
            var flag2 = ( point.Y < centerY && point.Y >= 0)?0:1;

            return (flag2 << 1) + flag1;
        }

        internal static void Split(Node<T> node)
        {
            var originX = node.Boundary.X;
            var originY = node.Boundary.Y;
            var originWidth = node.Boundary.Width;
            var originHeight = node.Boundary.Height;
            var halfWidth = originWidth / 2f;
            var halfHeight = originHeight / 2f;
            var centerX = originX + halfWidth;
            var centerY = originY + halfHeight;

            var nw = new Node<T>(new Boundary(originX,originY,halfWidth,halfHeight));
            var ne = new Node<T>(new Boundary(centerX,originY,halfWidth,halfHeight));
            var sw = new Node<T>(new Boundary(originX,centerY,halfWidth,halfHeight));
            var se = new Node<T>(new Boundary(centerX,centerY,halfWidth,halfHeight));
            node.NW = nw;
            node.NE = ne;
            node.SW = sw;
            node.SE = se;
            node.height++;
        }
        
        internal static void Insert(Node<T> node,NodeData<T> data,Boundary boundary)
        {
            if(node.count + 1 >= byte.MaxValue)
            {
                var dataArray = node.Value;
                node.Value = null;
                Split(node);
                foreach(var dataNode in dataArray)
                {
                    var index = Locate(node,dataNode.Boundary);
                    var newNode = node.NodeArray[index];
                    newNode.Value.Add(data);
                    newNode.count++;
                }
            }
            else
            {
                node.Value.Add(data);
            }
            node.count++;
        }

        #endregion

        internal Node<T> root;

        public QuadTree(Size size)
        {
            root = new Node<T>(new Boundary(Point.OriginPoint, size));
        }

        public void AddElement(Boundary boundary,NodeData<T> nodeData)
        {
            Insert(this.root, nodeData, boundary);
        }

        public void AddElement(Boundary boundary,T value)
        {
            Insert(this.root, new NodeData<T>(boundary, value), boundary);
        }
    }
}
